package leetcode101.search_problem.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code5
 * @Description 257. 二叉树的所有路径
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * <p>
 * 1
 * /   \
 * 2     3
 * \
 * 5
 * <p>
 * 输出: ["1->2->5", "1->3"]
 * <p>
 * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-07 10:40
 */
public class Code5 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*
    这个数据结构用来保存路径
     */
    static class QueueNode {
        TreeNode treeNode;
        QueueNode pre;
        QueueNode(TreeNode t, QueueNode p) {
            this.treeNode = t;
            this.pre = p;
        }
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        binaryTreePaths(root);
    }

    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>(); // 返回的结果
        List<QueueNode> temp =  new ArrayList<>(); // 保存的路径
        Queue<QueueNode> queue = new LinkedList<>(); // bfs的队列
        queue.offer(new QueueNode(root, null));
        while (!queue.isEmpty()) {
            QueueNode head = queue.poll();
            if (head.treeNode.left != null) {
                queue.offer(new QueueNode(head.treeNode.left, head));
            }
            if (head.treeNode.right != null) {
                queue.offer(new QueueNode(head.treeNode.right, head));
            }
            if (head.treeNode.left == null && head.treeNode.right == null) {
                temp.add(head);
            }
        }
        for (QueueNode q : temp) {
            StringBuilder ans = new StringBuilder();
            while (q.pre != null) {
                ans.insert(0, q.treeNode.val);
                ans.insert(0, "->");
                q = q.pre;
            }
            ans.insert(0, q.treeNode.val);
            res.add(ans.toString());
        }
        return res;
    }
}

/*
基本思路就是层数遍历，使用队列
 */